package leetcode

import (
	"Algorithms/sorts"
	"Algorithms/util"
	"container/heap"
	"fmt"
	"math"
	"sort"
	"strconv"
)

//二进制转10进制，能否被5整除，只需要看个位就行，因此每次运算只用个位
func PrefixesDivBy5(A []int) []bool {
	var result []bool
	var num int
	for _, v := range A {
		num = num*2 + v*1
		num = num % 10
		if num == 0 || num == 5 {
			result = append(result, true)
		} else {
			result = append(result, false)
		}
	}
	return result
}

//数组里找两个相加得目标值，利用map存储，时间复杂度n
func TwoSum(nums []int, target int) []int {
	m := make(map[int]int)
	var result []int
	for i, v := range nums {
		brother := target - v
		if index, ok := m[brother]; ok {
			result = append(result, index)
			result = append(result, i)
			return result
		}
		if _, ok := m[v]; !ok {
			m[v] = i
		}
	}
	return result
}

func TwoSumDoublePoint(nums []int, target int) []int {
	sorts.InsertionSort(nums)
	var result []int
	low := 0
	high := len(nums) - 1
	for low < high {
		if nums[high]+nums[low] == target {
			result = append(result, nums[low])
			result = append(result, nums[high])
			//去重
			for low < high && nums[low] == nums[low+1] {
				low++
			}
			low++
			for low < high && nums[high] == nums[high-1] {
				high--
			}
			high--
		} else if nums[high]+nums[low] < target {
			low++
		} else {
			high--
		}
	}
	return result
}

//删除有序数组中重复数，空间复杂度限制为1，利用原数组前段储存新数组，思路，新加索引作为新数组的实际索引
func removeDuplicates(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	p := 1
	for i := 1; i < len(nums); i++ {
		//思路类似于选择排序，选择一个不和前面重复的数字填充到前数组里
		for j := i - 1; j >= 0; j-- {
			if nums[j] == nums[i] {
				break
			}
			if j == 0 {
				nums[p] = nums[i]
				p++
			}
		}
	}
	return p
}

//是否是回文，思路，用翻转后的数字和原来数字比较
func IsPalindrome(x int) bool {
	if x < 0 {
		return false
	}
	y := 0
	temp := x
	for temp != 0 {
		y = y*10 + temp%10
		temp = temp / 10
	}
	if y != x {
		return false
	}
	return true
}

//找两个数组的中位数，利用归并排序里面的合并思想
func FindMedianSortedArrays(nums1 []int, nums2 []int) float64 {
	var numsall = make([]int, len(nums1)+len(nums2))
	var i, j, k int
	for k < len(numsall)/2+1 {
		if i >= len(nums1) {
			for j < len(nums2) {
				numsall[k] = nums2[j]
				k++
				j++
			}
			break
		}
		if j >= len(nums2) {
			for i < len(nums1) {
				numsall[k] = nums1[i]
				k++
				i++
			}
			break
		}
		if nums1[i] < nums2[j] {
			numsall[k] = nums1[i]
			i++
			k++
		} else {
			numsall[k] = nums2[j]
			j++
			k++
		}
	}
	if len(numsall)%2 == 0 {
		return float64(numsall[len(numsall)/2]+numsall[len(numsall)/2-1]) / 2
	} else {
		return float64(numsall[len(numsall)/2])
	}
}

//双指针法，求水桶最大容量，两边谁短谁缩长，寻找更大宽，复杂度N
func maxArea(height []int) int {
	if len(height) < 2 {
		return 0
	}
	var right = len(height) - 1
	var left = 0
	var maxWater int
	for left != right {
		if height[right] < height[left] {
			maxWater = max(maxWater, (right-left)*height[right])
			right--
		} else {
			maxWater = max(maxWater, (right-left)*height[left])
			left++
		}
	}
	return maxWater
}

//三数之和等于0，不得重复
//思路：固定一个数字之后，另外两个数字采取双指针法
func ThreeSum(nums []int) [][]int {
	//排序
	sorts.InsertionSort(nums)
	res := [][]int{}
	for i := 0; i < len(nums); i++ {
		//终结条件
		if nums[i] > 0 {
			break
		}
		//去重
		if i > 0 && nums[i] == nums[i-1] {
			continue
		}
		//双指针
		L := i + 1
		R := len(nums) - 1
		for L < R {
			sum := nums[i] + nums[L] + nums[R]
			if sum == 0 {
				//去重
				for L < R && nums[R] == nums[R-1] {
					R--
				}
				for L < R && nums[L] == nums[L+1] {
					L++
				}
				//因为不是返回角标，因此添加去重后的结果也无妨
				temp := []int{nums[i], nums[L], nums[R]}
				res = append(res, temp)
				//继续循环，因为可能还存在解
				R--
				L++
			} else if sum > 0 {
				R--
			} else {
				L++
			}
		}
	}
	return res
}

//16. 最接近的三数之和,暴力法
func threeSumClosest(nums []int, target int) int {
	diff := util.INT_MAX
	var res int

	for i := 0; i < len(nums); i++ {
		for j := i + 1; j < len(nums); j++ {
			for k := j + 1; k < len(nums); k++ {
				sum := nums[i] + nums[j] + nums[k]
				if util.Abs(target-sum) < diff {
					res = sum
					diff = util.Abs(sum - target)
				}
			}
		}
	}

	return res
}

//16. 最接近的三数之和,双指针法
func threeSumClosest2(nums []int, target int) int {
	sorts.InsertionSort(nums)
	var (
		best = util.INT_MAX
	)
	update := func(cur int) {
		if util.Abs(target-cur) < util.Abs(target-best) {
			best = cur
		}
	}
	for i := 0; i < len(nums)-2; i++ {
		j, k := i+1, len(nums)-1
		for j < k {
			sum := nums[i] + nums[j] + nums[k]
			if sum == target {
				return sum
			}
			update(sum)
			if sum < target {
				for j < k && nums[j] == nums[j+1] {
					j++
				}
				j++
			} else {
				for j < k && nums[k] == nums[k-1] {
					k--
				}
				k--
			}
		}
	}
	return best
}

//全排列，回溯法
//根据递归树估算，时间复杂度在O(n*n!)和O(n!)之间
func PrintPermutations(array []int, k int, sum *int) {
	if k == 1 {
		fmt.Print("[")
		for i, num := range array {
			fmt.Print(num)
			if i != len(array)-1 {
				fmt.Print(",")
			}
		}
		fmt.Println("]")
		*sum++
	}
	for i := 0; i < k; i++ {
		array[i], array[k-1] = array[k-1], array[i]
		PrintPermutations(array, k-1, sum)
		array[i], array[k-1] = array[k-1], array[i]
	}
}

//四数之和，不包含重复的，固定俩，双指针，和三数之和类似
func fourSum(nums []int, target int) [][]int {
	var res [][]int
	if len(nums) == 0 {
		return res
	}
	sorts.InsertionSort(nums)
	for a := 0; a <= len(nums)-4; a++ {
		for d := len(nums) - 1; a <= d-3; d-- {
			b := a + 1
			c := d - 1
			for b < c {
				temp := nums[a] + nums[b] + nums[c] + nums[d]
				if temp == target {
					res = append(res, []int{nums[a], nums[b], nums[c], nums[d]})
					for b < c && nums[b] == nums[b+1] {
						b++
					}
					for b < c && nums[c] == nums[c-1] {
						c--
					}
					b++
					c--
				} else if temp < target {
					b++
				} else {
					c--
				}
			}
			for a <= d-3 && nums[d] == nums[d-1] {
				d--
			}
		}
		for a < len(nums)-4 && nums[a] == nums[a+1] {
			a++
		}
	}
	return res
}

//判断井字游戏是否有效，规则问题
func validTicTacToe(board []string) bool {
	m := make(map[string]byte)
	winners := checkwinner(board)
	if len(winners) > 2 {
		return false
	}
	m[" "] = 0
	m["X"] = 0
	m["O"] = 0
	//统计xo下的总共步数
	for _, s := range board {
		for i := 0; i < len(s); i++ {
			m[string(s[i])]++
		}
	}
	//规则1，玩家轮流将字符放入空位（' '）中
	if m["X"] != m["O"] && m["X"] != m["O"]+1 {
		return false
	}
	//有两个胜者的时候，必须是x获胜，因为x可以一步连接两成3列
	if len(winners) == 2 && winners[0] != winners[1] {
		return false
	}
	if len(winners) == 2 && winners[0] == "X" && m["X"] == m["O"]+1 {
		return true
	}
	//x获胜的条件是必o多一步
	if len(winners) == 1 && winners[0] == "X" && m["X"] != m["O"]+1 {
		return false
	}
	//o获胜的条件是和x一样多
	if len(winners) == 1 && winners[0] == "O" && m["X"] != m["O"] {
		return false
	}
	return true
}

//找到获胜者
func checkwinner(b []string) []string {
	var winners []string
	if string(b[1][1]) != " " {
		if b[0][0] == b[1][1] && b[0][0] == b[2][2] {
			winners = append(winners, string(b[0][0]))
		}
		if b[0][1] == b[1][1] && b[0][1] == b[2][1] {
			winners = append(winners, string(b[0][1]))
		}
		if b[1][0] == b[1][1] && b[1][0] == b[1][2] {
			winners = append(winners, string(b[1][0]))
		}
		if b[2][0] == b[1][1] && b[2][0] == b[0][2] {
			winners = append(winners, string(b[2][0]))
		}
	}
	if string(b[0][0]) != " " {
		if b[0][0] == b[0][1] && b[0][0] == b[0][2] {
			winners = append(winners, string(b[0][0]))
		}
		if b[0][0] == b[1][0] && b[0][0] == b[2][0] {
			winners = append(winners, string(b[0][0]))
		}
	}
	if string(b[2][2]) != " " {
		if b[0][2] == b[1][2] && b[0][2] == b[2][2] {
			winners = append(winners, string(b[0][2]))
		}
		if b[2][0] == b[2][1] && b[2][0] == b[2][2] {
			winners = append(winners, string(b[2][0]))
		}
	}
	return winners
}

//506. 相对名次
func findRelativeRanks(score []int) []string {
	res := make([]string, len(score))
	if len(score) == 0 {
		return res
	}
	//用哈希表记录数字的原始index
	m := make(map[int]int)
	//插入排序，从大到小，并且记录一下原始index
	for i := len(score) - 1; i >= 0; i-- {
		j := i + 1
		temp := score[i]
		m[temp] = i
		for ; j < len(score); j++ {
			if score[j] > temp {
				score[j-1] = score[j]
			} else {
				break
			}
		}
		score[j-1] = temp
	}
	//发奖牌，参考原始index
	for i, v := range score {
		if i == 0 {
			res[m[v]] = "Gold Medal"
		} else if i == 1 {
			res[m[v]] = "Silver Medal"
		} else if i == 2 {
			res[m[v]] = "Bronze Medal"
		} else {
			res[m[v]] = strconv.Itoa(i + 1)
		}
	}
	return res
}

//419. 甲板上的战舰
func countBattleships(board [][]byte) int {
	sum := 0
	bx := []byte("X")[0]
	b0 := []byte(".")[0]
	for i := 0; i < len(board); i++ {
		for j := 0; j < len(board[i]); j++ {
			if board[i][j] == bx {
				sum++
				//排除同一舰的可能性
				for a := i + 1; a < len(board); a++ {
					if board[a][j] == bx {
						board[a][j] = b0
					} else {
						break
					}
				}
				for b := j + 1; b < len(board[i]); b++ {
					if board[i][b] == bx {
						board[i][b] = b0
					} else {
						break
					}
				}
			}
		}
	}
	return sum
}

//475. 供暖器
//对于每个房屋，要么用前面的暖气，要么用后面的，二者取近的，得到距离；
//对于所有的房屋，选择最大的上述距离。
func findRadius(houses []int, heaters []int) int {
	sort.Ints(houses)
	sort.Ints(heaters)
	if len(heaters) == 1 {
		return max(abs(heaters[0]-houses[0]), abs(heaters[0]-houses[len(houses)-1]))
	}
	j := 0
	maxLen := 0
	for _, v := range houses {
		for j < len(heaters)-1 && v >= heaters[j] {
			j++
		}
		if j == 0 {
			//前后设备选一个最小距离作为供暖设备
			temp := min(abs(heaters[j]-v), abs(heaters[j+1]-v))
			//找到最大供暖距离
			maxLen = max(temp, maxLen)
		} else {
			//前后设备选一个最小距离作为供暖设备
			temp := min(abs(heaters[j]-v), abs(heaters[j-1]-v))
			//找到最大供暖距离
			maxLen = max(temp, maxLen)
		}
	}
	return maxLen
}

func max(a, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}

func abs(i int) int {
	if i < 0 {
		return i * (-1)
	}
	return i
}

func min(a, b int) int {
	if a < b {
		return a
	} else {
		return b
	}
}

func jump(nums []int) int {
	n := len(nums)
	minStep := make([]int, n)
	for i := n - 2; i >= 0; i-- {
		if nums[i]+i >= n-1 {
			minStep[i] = 1 + minStep[n-1]
		} else {
			min := n
			for j := i + 1; j <= i+nums[i]; j++ {
				if minStep[j] < min {
					min = minStep[j]
				}
			}
			minStep[i] = 1 + min
		}
	}
	return minStep[0]
}

//1995. 统计特殊四元组，暴力法
func countQuadruplets(nums []int) int {
	sum := 0
	n := len(nums)
	for i := 0; i < n-3; i++ {
		for j := i + 1; j < n-2; j++ {
			for k := j + 1; k < n-1; k++ {
				for x := k + 1; x < n; x++ {
					if nums[i]+nums[j]+nums[k] == nums[x] {
						sum++
					}
				}
			}
		}
	}
	return sum
}

//846. 一手顺子,用队列
func isNStraightHand(hand []int, groupSize int) bool {
	n := len(hand)
	if n%groupSize != 0 {
		return false
	}
	sort.Ints(hand)
	m := map[int]int{}
	for i := 0; i < n; i++ {
		m[hand[i]]++
	}
	for i := 0; i < n; i++ {
		if m[hand[i]] == 0 {
			continue
		}
		for j := 0; j < groupSize; j++ {
			if m[hand[i]+j] == 0 {
				return false
			}
			m[hand[i]+j]--
		}
	}
	return true
}

//66. 加一
func plusOne(digits []int) []int {
	for i := len(digits) - 1; i >= 0; i-- {
		digits[i]++
		if digits[i] == 10 {
			digits[i] = 0
		} else {
			break
		}
		if i == 0 {
			digits = append([]int{1}, digits...)
		}
	}
	return digits
}

//27. 移除元素
func removeElement(nums []int, val int) int {
	sum := 0
	index := 0
	for j := 0; j < len(nums); j++ {
		if nums[j] != val {
			nums[j], nums[index] = nums[index], nums[j]
			index++
			sum++
		}
	}
	nums = nums[sum:]
	return sum
}

//41. 缺失的第一个正数
func firstMissingPositive(nums []int) int {
	index := 0
	for index < len(nums) {
		//hash映射，每个数字如果有就映射到数组相同的位置上
		if nums[index] > 0 && nums[index] <= len(nums) && nums[nums[index]-1] != nums[index] {
			nums[nums[index]-1], nums[index] = nums[index], nums[nums[index]-1]
			continue
		}
		index++
	}
	for i := range nums {
		if nums[i] != i+1 {
			return i + 1
		}
	}
	return len(nums) + 1
}

//219. 存在重复元素 II
func containsNearbyDuplicate(nums []int, k int) bool {
	m := make(map[int]int)
	for i, v := range nums {
		if _, ok := m[nums[i]]; ok {
			if i-m[v] <= k {
				return true
			}
		}
		m[v] = i
	}
	return false
}

//54. 螺旋矩阵
func spiralOrder(matrix [][]int) []int {
	m := len(matrix)
	n := len(matrix[0])
	res := make([]int, m*n)
	var f func(int, int, int)
	f = func(i, j, index int) {
		if index >= len(res) {
			return
		}
		offset := i
		for index < len(res) {
			res[index] = matrix[i][j]
			if j == n-offset-1 {
				break
			}
			index++
			j++
		}
		for index < len(res) {
			res[index] = matrix[i][j]
			if i == m-offset-1 {
				break
			}
			index++
			i++
		}
		for index < len(res) {
			res[index] = matrix[i][j]
			if j == offset {
				break
			}
			index++
			j--
		}
		for index < len(res) {
			res[index] = matrix[i][j]
			if i == offset+1 {
				break
			}
			index++
			i--
		}
		f(i, j+1, index+1)
	}
	f(0, 0, 0)
	return res
}

//59. 螺旋矩阵 II
func generateMatrix(n int) [][]int {
	res := make([][]int, n)
	for i := range res {
		res[i] = make([]int, n)
	}
	var f func(int, int, int)
	f = func(i, j, index int) {
		if index > n*n {
			return
		}
		offset := i
		for index <= n*n {
			res[i][j] = index
			if j == n-offset-1 {
				break
			}
			index++
			j++
		}
		for index <= n*n {
			res[i][j] = index
			if i == n-offset-1 {
				break
			}
			index++
			i++
		}
		for index <= n*n {
			res[i][j] = index
			if j == offset {
				break
			}
			index++
			j--
		}
		for index <= n*n {
			res[i][j] = index
			if i == offset+1 {
				break
			}
			index++
			i--
		}
		f(i, j+1, index+1)
	}
	f(0, 0, 1)
	return res
}

//2029. 石子游戏 IX
func stoneGameIX(stones []int) bool {
	m := make(map[int]int)
	for _, k := range stones {
		m[k%3]++
	}
	if m[1] == 0 && m[2] == 0 {
		return false
	}
	var f = func(b, c, firstGet int) int {
		res := 0
		sum := 0
		if firstGet == 1 {
			if b > 0 {
				b--
				res++
				sum = 1
			} else {
				return 0
			}

		} else {
			if c > 0 {
				c--
				res++
				sum = 2
			} else {
				return 0
			}
		}
		for {
			if sum == 1 {
				if b == 0 {
					break
				}
				b--
				sum = (sum + 1) % 3
			} else {
				if c == 0 {
					break
				}
				c--
				sum = (sum + 2) % 3
			}
			res++
		}
		if b == 0 && c == 0 {
			return 0
		}
		//如果返回是1，则bob没石头可抓，如果是0，则alice没石头可抓
		return res
	}
	res1 := f(m[1], m[2], 1)
	res2 := f(m[1], m[2], 2)
	if m[0]%2 != 0 {
		if res1 != 0 {
			res1++
		}
		if res2 != 0 {
			res2++
		}
	}
	if res1%2 == 1 || res2%2 == 1 {
		return true
	}
	return false
}

//56. 合并区间
func merge(intervals [][]int) [][]int {
	sort.Slice(intervals, func(i, j int) bool {
		return intervals[i][0] < intervals[j][0]
	})
	var merged [][]int
	merged = append(merged, intervals[0])
	for i := 1; i < len(intervals); i++ {
		//重合
		if intervals[i][0] <= merged[len(merged)-1][1] {
			if intervals[i][1] > merged[len(merged)-1][1] {
				merged[len(merged)-1][1] = intervals[i][1]
			}
		} else {
			merged = append(merged, intervals[i])
		}
	}
	return merged
}

//57. 插入区间
func insert(intervals [][]int, newInterval []int) [][]int {
	intervals = append(intervals, newInterval)
	sort.Slice(intervals, func(i, j int) bool {
		return intervals[i][0] < intervals[j][0]
	})
	return merge(intervals)
}

func removePalindromeSub(s string) int {
	for i := 0; i < len(s)/2; i++ {
		if s[i] != s[len(s)-1-i] {
			return 2
		}
	}
	return 1
}

//73. 矩阵置零
func setZeroes(matrix [][]int) {
	m := len(matrix)
	n := len(matrix[0])
	row := make([]bool, m)
	column := make([]bool, n)
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if matrix[i][j] == 0 {
				row[i] = true
				column[j] = true
			}
		}
	}
	for i := range row {
		if row[i] {
			for j := range matrix[i] {
				matrix[i][j] = 0
			}
		}
	}
	for i := range column {
		if column[i] {
			for j := range matrix {
				matrix[j][i] = 0
			}
		}
	}
}

//1725. 可以形成最大正方形的矩形数目
func countGoodRectangles(rectangles [][]int) int {
	m := make(map[int]int)
	min := func(a, b int) int {
		if a < b {
			return a
		}
		return b
	}
	maxLenth := 0
	for i := 0; i < len(rectangles); i++ {
		lenth := min(rectangles[i][0], rectangles[i][1])
		if lenth > maxLenth {
			maxLenth = lenth
		}
		m[lenth]++
	}
	return m[maxLenth]
}

//169. 多数元素
func majorityElement(nums []int) int {
	sort.Ints(nums)
	i, j := 0, 0
	for i <= j && j < len(nums) {
		if nums[j] != nums[i] {
			i++
		} else {
			if j-i+1 > len(nums)/2 {
				return nums[i]
			}
			j++
		}
	}
	return -1
}

//48. 旋转图像,顺时针90°
func rotate(matrix [][]int) {
	n := len(matrix)
	if n%2 != 0 {
		for i := 0; i < n/2; i++ {
			matrix[n/2][n-1-i], matrix[n-1-i][n-1-n/2], matrix[n-1-n/2][i], matrix[i][n/2] =
				matrix[i][n/2], matrix[n/2][n-1-i], matrix[n-1-i][n-1-n/2], matrix[n-1-n/2][i]
		}
	}
	for i := 0; i < n/2; i++ {
		for j := 0; j < n/2; j++ {
			matrix[j][n-1-i], matrix[n-1-i][n-1-j], matrix[n-1-j][i], matrix[i][j] =
				matrix[i][j], matrix[j][n-1-i], matrix[n-1-i][n-1-j], matrix[n-1-j][i]

		}
	}
}

//747. 至少是其他数字两倍的最大数
func dominantIndex(nums []int) int {
	a, b := math.MinInt32, math.MinInt32
	a_index := -1
	for i := range nums {
		if nums[i] > a {
			b = a
			a = nums[i]
			a_index = i
		} else if nums[i] > b {
			b = nums[i]
		} else {
			continue
		}
	}
	if a >= 2*b {
		return a_index
	}
	return -1
}

//373. 查找和最小的 K 对数字，优先级队列
func kSmallestPairs(nums1 []int, nums2 []int, k int) [][]int {
	m, n := len(nums1), len(nums2)
	hp := hp{
		index: []pairNum1Num2{},
	}
	res := [][]int{}
	for i := 0; i < m && i < k; i++ {
		heap.Push(&hp, pairNum1Num2{i, 0, nums1[i] + nums2[0]})
	}
	for len(res) < k && hp.Len() > 0 {
		p := heap.Pop(&hp).(pairNum1Num2)
		res = append(res, []int{nums1[p.i], nums2[p.j]})
		if p.j+1 < n {
			//i+1已经添加进优先级队列了，所以这里只需添加j+1
			heap.Push(&hp, pairNum1Num2{p.i, p.j + 1, nums1[p.i] + nums2[p.j+1]})
		}
	}
	return res
}

type pairNum1Num2 struct {
	i, j int
	sum  int
}
type hp struct {
	index []pairNum1Num2
}

func (h *hp) Push(x interface{}) {
	h.index = append(h.index, x.(pairNum1Num2))
}

func (h *hp) Pop() interface{} {
	res := h.index[len(h.index)-1]
	tmp := h.index
	h.index = tmp[:len(h.index)-1]
	return res
}

func (h hp) Len() int {
	return len(h.index)
}

func (h hp) Less(i, j int) bool {
	return h.index[i].sum < h.index[j].sum
}

func (h hp) Swap(i, j int) {
	h.index[i], h.index[j] = h.index[j], h.index[i]
}

//128. 最长连续序列
func longestConsecutive(nums []int) int {
	m := make(map[int]int)
	ans := 0
	for _, k := range nums {
		if _, ok := m[k]; !ok {
			left, right := m[k-1], m[k+1]
			//只管两头
			m[k] = 1 + left + right
			m[k-left] = m[k]
			m[k+right] = m[k]
			if m[k] > ans {
				ans = m[k]
			}
		}
	}
	return ans
}
//84. 柱状图中最大的矩形
func largestRectangleArea(heights []int) int {
	//维护单调增的栈
	stack := []int{}
	n := len(heights)
	left, right := make([]int, n), make([]int, n)
	for i := 0; i < n; i++ {
		for len(stack) > 0 && heights[stack[len(stack)-1]] >= heights[i] {
			stack = stack[:len(stack)-1]
		}
		if len(stack) == 0 {
			left[i] = -1
		} else {
			//比i矮的第一个
			left[i] = stack[len(stack)-1]
		}
		stack = append(stack, i)
	}
	stack = []int{}
	for i := n - 1; i >= 0; i-- {
		for len(stack) > 0 && heights[stack[len(stack)-1]] >= heights[i] {
			stack = stack[:len(stack)-1]
		}
		if len(stack) == 0 {
			right[i] = n
		} else {
			//比i矮的第一个
			right[i] = stack[len(stack)-1]
		}
		stack = append(stack, i)
	}
	ans := 0
	for i := range heights {
		temp := heights[i] * (right[i] - left[i] - 1)
		if ans < temp {
			ans = temp
		}
	}
	return ans
}

func subsets(nums []int) [][]int {
	n := len(nums)
	res := make([][]int, 0)
	var f func(int, []int)
	f = func(i int, arr []int) {
		if i == n {
			tmp := make([]int, len(arr))
			copy(tmp, arr)
			res = append(res, tmp)
			return
		}
		f(i+1, arr)
		f(i+1, append(arr, nums[i]))
	}
	f(0, []int{})
	return res
}

//31. 下一个排列
func nextPermutation(nums []int) {
	n := len(nums)
	i := n - 2
	for ; i >= 0; i-- {
		if nums[i] < nums[i+1] {
			break
		}
	}
	if i == -1 {
		sort.Ints(nums)
	} else {
		for j := i + 1; j <= n; j++ {
			if j == n || nums[j] <= nums[i] {
				nums[i], nums[j-1] = nums[j-1], nums[i]
				break
			}
		}
		sort.Ints(nums[i+1:])
	}
}

func sortColors(nums []int) {
	h0, h1 := 0, 0
	for i, k := range nums {
		if k == 0 {
			nums[h0], nums[i] = nums[i], nums[h0]
			if h0 < h1 {
				nums[h1], nums[i] = nums[i], nums[h1]
			}
			h0++
			h1++
		} else if k == 1 {
			nums[h1], nums[i] = nums[i], nums[h1]
			h1++
		}
	}
}

//581. 最短无序连续子数组，两边单调增，找中间的长度
func findUnsortedSubarray(nums []int) int {
	min, max := math.MaxInt32, math.MinInt32
	left, right := len(nums), 0
	for i := 0; i < len(nums); i++ {
		if nums[i] < max {
			right = i
		} else {
			max = nums[i]
		}
	}
	for i := len(nums) - 1; i >= 0; i-- {
		if nums[i] > min {
			left = i
		} else {
			min = nums[i]
		}
	}
	if left > right {
		return 0
	}
	return right - left + 1
}

//560. 和为 K 的子数组，双指针？
func subarraySum(nums []int, k int) int {
	ans := 0
	for i := range nums {
		sum := 0
		for j := i; j >= 0; j-- {
			sum += nums[j]
			if sum == k {
				ans++
			}
		}
	}
	return ans
}
//85. 最大矩形
func maximalRectangle(matrix [][]byte) int {
	m, n := len(matrix), len(matrix[0])
	ans := 0
	for i := 0; i < m; i++ {
		height := make([]int, n)
		for j := 0; j < n; j++ {
			if matrix[i][j] == '1' {
				temp := 1
				for k := i - 1; k >= 0; k-- {
					if matrix[k][j] == '1' {
						temp++
					} else {
						break
					}
				}
				height[j] = temp
			}
		}
		temp := largestRectangleArea(height)
		if temp > ans {
			ans = temp
		}
	}
	return ans
}

func findKthLargest(nums []int, k int) int {
	sort.Ints(nums)
	return nums[len(nums)-k]
}

//283. 移动零
func moveZeroes(nums []int) {
	n := len(nums)
	index0 := n
	for i := n - 1; i >= 0; i-- {
		if nums[i] == 0 {
			for j := i + 1; j < index0; j++ {
				nums[j-1] = nums[j]
			}
			nums[index0-1] = 0
			index0--
		}
	}
}

//287. 寻找重复数 ,龟兔赛跑
func findDuplicate(nums []int) int {
	slow, fast := 0, 0
	for slow == 0 || slow != fast {
		slow = nums[slow]
		fast = nums[fast]
		fast = nums[fast]
	}
	head1, head2 := 0, slow
	for head1 != head2 {
		head1 = nums[head1]
		head2 = nums[head2]
	}
	return head1
}

//448. 找到所有数组中消失的数字
func findDisappearedNumbers(nums []int) []int {
	i := 0
	for i < len(nums) {
		temp := nums[i]
		if temp != i+1 && temp != nums[temp-1] {
			nums[i], nums[temp-1] = nums[temp-1], nums[i]
		} else {
			i++
		}
	}
	ans := []int{}
	for i := range nums {
		if nums[i] != i+1 {
			ans = append(ans, i+1)
		}
	}
	return ans
}

//406. 根据身高重建队列
func reconstructQueue(people [][]int) [][]int {
	sort.Slice(people, func(i, j int) bool {
		if people[i][0] < people[j][0] {
			return true
		} else if people[i][0] == people[j][0] {
			return people[i][1] > people[j][1]
		}
		return false
	})
	fmt.Println(people)
	res := make([][]int, 0)
	for i := len(people) - 1; i >= 0; i-- {
		index := people[i][1]
		res = append(res[:index], append([][]int{people[i]}, res[index:]...)...)
	}
	return res
}

//347. 前 K 个高频元素
func topKFrequent(nums []int, k int) []int {
	sort.Ints(nums)
	h:=&hps{
		array: []hpk{},
	}
	heap.Init(h)
	for i:=0;i<len(nums);{
		j:=i+1
		for ;j<len(nums);j++{
			if nums[i]!=nums[j]{
				break
			}
		}
		heap.Push(h,hpk{
			freq: j-i,
			val:  nums[i],
		})
		if h.Len()>k{
			heap.Pop(h)
		}
		i=j
	}
	res:=[]int{}
	for i:=0;i<h.Len();i++{
		res=append(res, h.array[i].val)
	}
	return res
}

type hpk struct {
	freq int
	val  int
}
type hps struct {
	array []hpk
}

func (h hps) Len() int {
	return len(h.array)
}

func (h hps) Less(i, j int) bool {
	return h.array[i].freq<h.array[j].freq
}

func (h hps) Swap(i, j int) {
	h.array[i],h.array[j]=h.array[j],h.array[i]
}

func (h *hps) Push(x interface{}) {
	h.array=append(h.array, x.(hpk))
}

func (h *hps) Pop() interface{} {
	top:=h.array[h.Len()-1]
	new:=h.array[:h.Len()-1]
	h.array=new
	return top
}
//416. 分割等和子集
func canPartition(nums []int) bool {
	var sum int
	for i:=range nums{
		sum+=nums[i]
	}
	if sum%2!=0{
		return false
	}
	sort.Ints(nums)
	target:=sum/2
	//dp:=make([]bool,target+1)
	visited:=make([][]int,len(nums))
	for i:=range visited{
		visited[i]=[]int{}
	}
	found:=false
	var f func(i,sum int)
	check:=func(arr []int,key int)bool{
		if arr==nil{
			return false
		}
		for i:=range arr{
			if arr[i]==key{
				return true
			}
		}
		return false
	}
	f= func(i,sum int) {
		if sum==target{
			found=true
			return
		}
		if found||i==len(nums){
			return
		}
		if check(visited[i],sum){
			return
		}
		visited[i]=append(visited[i], sum)
		f(i+1,sum+nums[i])
		f(i+1,sum)
	}
	f(0,0)
	return found
}